\subsubsection{Übung (vii)}

\paragraph{Aufgabe:}
Es sei $p$ eine Primzahl, $p > \ell$ und $\ell$ Paare $(x_i, y_i)_{1 \le i \le \ell}$ von Elementen aus $\Z/p\Z$ mit paarweise verschiedenen $x_i$ gegeben. Beweisen Sie, dass es genau ein Polynom $b(X)$ mit $\deg b < \ell$ gibt, welches $b(x_i) = y_i$ für alle $1 \le i \le \ell$ erfüllt.

\textit{Hinweis:} Die Existenz eines solchen Polynoms ist klar, da man für $b(X)$ das Lagrange-Interpolations\-polynom verwenden kann. Nehmen Sie an, es gäbe ein zweites Polynom $a(X) \ne b(X)$, welches die Voraussetzungen erfüllt und führen Sie diese Annahme zum Widerspruch.

\paragraph{Lösung:}
Es gelten folgende Voraussetzungen
\begin{itemize}
\item Es ist p eine Primzahl mit p $> \ell$
\item Es gibt $\ell$ Paare ($x_{i},y_{i}$), $1 \leq i \leq \ell$ mit paarweise verschiedenen $x_{i}$
\item Wähle deg $\ell-1$ für $b(X)$ und $a(X)$
\end{itemize}

Damit lassen sich die beiden Polynome $b(X)$ und $a(X)$ in der Standardbasis schreiben, was zu folgender Darstellung führt:

\[
b(X) = b_{0} + \sum_{j=1}^{\ell-1} b_{j} X^j
\]
\[
a(X) = a_{0} + \sum_{j=1}^{\ell-1} a_{j} X^j
\]

Es wird nun angenommen, dass $b(X) \neq a(X)$ gilt. Dazu wird ein weiteres Polynom $c(X)$ betrachtet, wofür gilt:

\[
c(X) = b(x) - a(X) = \sum_{i=0}^{\ell-1} (b_i - a_i) X^i
\]

Aus der Darstellung kann nun abgelesen werden, dass der Grad $\deg c(X)$ höchstens $\ell - 1$ betragen kann. Da ein Polynom über einem Körper höchstens so viele Nullstellen haben kann, wie dessen Grad angibt, kann $c(X)$ höchstens $\ell - 1$ Nullstellen besitzen. Jedoch gilt $c(x_i) = b(x_i) - a(x_i) = y_i - y_i = 0$ für alle $1 \le i \le \ell$. Demnach hätte $c(X)$ also $\ell$ Nullstellen. Dies führt zum Widerspruch der Annahme $b(X) \neq a(X)$

Es ist nun zu widerlegen, dass $b(X) = a(X)$ gilt.